package q752_openLock;

import java.util.*;

public class Solution {
    /*
    打开转盘锁
    此题的模板与433题基本一致
    都是使用BFS 具体步骤可以直接参照433题
     */
    public int openLock(String[] deadends, String target) {
        if ("0000".contains(target)) {
            return 0;
        }
        Set<String> deadSet = new HashSet<>(Arrays.asList(deadends));
        if (deadSet.contains("0000")) {
            return -1;
        }
        Set<String> visited = new HashSet<>();
        Deque<String> queue = new LinkedList<>();
        // 数字可能的变化方式 ： +1 或者 -1
        int[] dir = {1, -1};
        int step = 1;
        visited.add("0000");
        queue.offer("0000");
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                String curNum = queue.poll();

                for (int j = 0; j < 4; j++) {
                    for (int k = 0; k < 2; k++) {
                        StringBuilder sb = new StringBuilder(curNum);
                        int changeNum = sb.charAt(j) - '0';
                        changeNum = changeNum == 0 && dir[k] == -1 ? 9 : (changeNum + dir[k]) % 10;
                        sb.setCharAt(j, (char) (changeNum + 48));
                        String next = sb.toString();
                        if (!visited.contains(next) && !deadSet.contains(next)) {
                            if (next.equals(target)) {
                                return step;
                            }
                            visited.add(next);
                            queue.offer(next);
                        }
                    }
                }
            }
            step++;
        }

        return -1;
    }
}
